# coding=utf-8
#*****************************************************************************
#       Copyright (C) 2008 Sébastien Labbé <slabqc@gmail.com>
#
#  Distributed under the terms of the GNU General Public License version 2 (GPLv2)
#
#  The full text of the GPLv2 is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from utils import isint
from itertools import imap, ifilterfalse
from sage.structure.sage_object import SageObject
from sage.words.word import Words, FiniteWord
from sage.words.alpha import Alphabet

class WordMorphism(SageObject):
    r"""
    TESTS:
        sage: wm = WordMorphism('a->ab,b->ba')
        sage: wm == loads(dumps(wm))
        True
    """
    def __init__(self, data, codomain=None):
        r"""
        Construction of the morphism.
        
        EXAMPLES:
            sage: thuemorse = WordMorphism('a->ab,b->ba')
            sage: fibo = WordMorphism('0->01,1->1')
            sage: WordMorphism({"a":"ab","b":"ba"})
            WordMorphism('a->ab,b->ba')
            sage: WordMorphism('a->ab,b->ba')
            WordMorphism('a->ab,b->ba')
            sage: WordMorphism('a->ab,') 
            WordMorphism('a->ab')
            sage: WordMorphism(',a->ab,,,b->ba,,')
            WordMorphism('a->ab,b->ba')
            sage: WordMorphism('a->ab,b->')
            WordMorphism('a->ab,b->')
            sage: WordMorphism('a->ab,b-')
            Traceback (most recent call last):
            ...
            ValueError: The second and third characters must be '->' (not '-')
            sage: WordMorphism('a->ab,b') 
            Traceback (most recent call last):
            ...
            ValueError: The second and third characters must be '->' (not '')
            sage: WordMorphism('a->ab,a-]asdfa')
            Traceback (most recent call last):
            ...
            ValueError: The second and third characters must be '->' (not '-]')
            sage: WordMorphism('a->ab,a->ba')
            Traceback (most recent call last):
            ...
            ValueError: The image of 'a' is defined twice.
        
        TESTS:
            sage: WordMorphism(WordMorphism('a->ab,b->ba'))
            WordMorphism('a->ab,b->ba')
        """
        if isinstance(data, WordMorphism):
            self._domain = data._domain
            self._codomain = data._codomain
            self._morph = data._morph
        else:
            if isinstance(data, str):
                data = self._build_dict(data)
            elif not isinstance(data, dict):
                raise NotImplementedError
            
            if codomain is None:
                codomain = self._build_codomain(data)

            if not isinstance(codomain, Words):
                raise TypeError, "the codomain must be a Words domain"
            self._codomain = codomain
            
            self._morph = {}
            
            dom_alph = list()
            cod = self._codomain
            for (key,val) in data.iteritems():
                dom_alph.append(key)
                self._morph[key] = cod(val)
            
            dom_alph.sort()
            self._domain = Words(dom_alph)
    
    def _build_dict(self, s):
        r"""
        Parse the string input to WordMorphism and build the dictionary 
        it represents.
        
        TESTS:
            sage: wm = WordMorphism('a->ab,b->ba')
            sage: wm._build_dict('a->ab,b->ba') == {'a': 'ab', 'b': 'ba'}
            True
            sage: wm._build_dict('a->ab,a->ba')
            Traceback (most recent call last):
            ...
            ValueError: The image of 'a' is defined twice.
            sage: wm._build_dict('a->ab,b>ba')
            Traceback (most recent call last):
            ...
            ValueError: The second and third characters must be '->' (not '>b')
        """
        tmp_dict = {}
        for fleche in s.split(','):
            if len(fleche) == 0:
                continue
            
            if len(fleche) < 3 or fleche[1:3] != '->':
                raise ValueError, "The second and third characters must be '->' (not '%s')"%fleche[1:3]
            
            lettre = fleche[0]
            image  = fleche[3:]
            
            if lettre in tmp_dict:
                raise ValueError, "The image of %r is defined twice." %lettre
            
            tmp_dict[lettre] = image
        return tmp_dict

    def _build_codomain(self, data):
        r"""
        Returns a Words domain containing all the letter in the keys of 
        data (which must be a dictionnary).
        
        TESTS:
            sage: wm = WordMorphism('a->ab,b->ba')
            sage: wm._build_codomain({'a': 'ab', 'b': 'ba'})
            Words over {'a', 'b'}
            sage: wm._build_codomain({'a': 'dcb', 'b': 'a'})
            Words over {'a', 'b', 'c', 'd'}
        """
        codom_alph = set()
        for val in data.itervalues():
            codom_alph.update(val)
        l = list(codom_alph)
        l.sort()
        return Words(l)
        
    def __eq__(self, other):
        r"""
        Return True if the receiver is equal to other.
        
        EXAMPLES:
            sage: n = WordMorphism('a->a,b->aa,c->aaa')
            sage: n**3 == n**1
            True
            sage: WordMorphism('b->ba,a->ab') == WordMorphism('a->ab,b->ba')
            True
            sage: WordMorphism('b->ba,a->ab') == WordMorphism({"a":"ab","b":"ba"})
            True
        """
        return self._morph == other._morph
    
    def __repr__(self):
        r"""
        Return the morphism in str (for display).
        
        EXAMPLES:
            sage: WordMorphism('a->ab,b->ba')
            WordMorphism('a->ab,b->ba')
            sage: WordMorphism('b->ba,a->ab')
            WordMorphism('a->ab,b->ba')
        """
        l = [str(lettre) + '->' + image.string_rep() for lettre,image in self._morph.iteritems()]
        l.sort()
        return "WordMorphism('%s')" % ','.join(l)
    
    def __call__(self, w, order=1):
        r"""
        Return the image of w of the given order under the morphism receiver.
        
        EXAMPLES:
            sage: m=WordMorphism('a->ab,b->ba')
            sage: m(Words('a')('a'))
            word: ab
            sage: m(Words('a')('aa'))
            word: abab
            sage: m(Words('ab')('aaab'))
            word: abababba
            sage: m(Words('01')())
            word: 
            sage: m(Words('01')('0'))
            Traceback (most recent call last):
            ...
            TypeError: cannot apply to incompatible set
            sage: m(Words('abc')('aabbc'))
            Traceback (most recent call last):
            ...
            TypeError: cannot apply to incompatible set
            sage: m(Words('ab')('a'), -1)
            Traceback (most recent call last):
            ...
            ValueError: order (-1) must be a positive integer
            sage: m(Words('ab')('a'), 6.7)
            Traceback (most recent call last):
            ...
            TypeError: order must be an integer
            sage: m(Words('a')('a'))
            word: ab
            sage: m(Words('a')('a'), 0)
            word: a
            sage: for i in range(8):
            ...     m(Words('ab')('a'), i)
            ...     
            word: a
            word: ab
            word: abba
            word: abbabaab
            word: abbabaabbaababba
            word: abbabaabbaababbabaababbaabbabaab
            Finite word of length 64 over {'a', 'b'}
            Finite word of length 128 over {'a', 'b'}
        """
        try:
            w = self._domain(w)
        except:
            raise TypeError, "cannot apply to incompatible set"
        
        if not isint(order):
            raise TypeError, "order must be an integer"
        
        elif order < 0 :
            raise ValueError, "order (%s) must be a positive integer" % order
        elif order == 0:
            return w
        elif order == 1:        
            return reduce(lambda r, x: r*x, 
                          imap(self._morph.get, w), 
                          self._codomain())
        elif order > 1:
            return self(self(w, order-1))
    
    def __mul__(self, other):
        r"""
        Return the morphism receiver*other
        
        EXAMPLES:
            sage: m = WordMorphism('a->ab,b->ba')
            sage: fibo = WordMorphism('a->ab,b->a')
            sage: fibo*m
            WordMorphism('a->aba,b->aab')
            sage: fibo*fibo
            WordMorphism('a->aba,b->ab')
            sage: m*fibo
            WordMorphism('a->abba,b->ab')
            sage: m = WordMorphism('a->ab,b->ba')
            sage: n = WordMorphism('a->a,b->aa,c->aaa')
            sage: p1 = n*m; p2 = m*n
            sage: p1
            WordMorphism('a->aaa,b->aaa')
            sage: p1.domain()
            Words over {'a', 'b'}
            sage: p1.codomain()
            Words over {'a'}
            sage: p2
            WordMorphism('a->ab,b->abab,c->ababab')
            sage: p2.domain()
            Words over {'a', 'b', 'c'}
            sage: p2.codomain()
            Words over {'a', 'b'}
            sage: m = WordMorphism('a->b,b->c,c->a')
            sage: WordMorphism('')*m            
            Traceback (most recent call last):
            ...
            TypeError: cannot apply to incompatible set
            sage: m*WordMorphism('')
            WordMorphism('')
        """
        #TODO : Est-ce que c'est le comportement que l'on veut pour le produit 
        #par le morphisme vide? Voir lignes ci-haut.
        return WordMorphism(dict((key, self(w)) for (key, w) in other._morph.iteritems()))
    
    def __pow__(self, exp):
        r"""
        Return the power of the receiver with exponent = exp.
        
        EXAMPLES:
            sage: m = WordMorphism('a->ab,b->ba')
            sage: m^1.5
            Traceback (most recent call last):
              ...
            ValueError: exponent (1.50000000000000) must be an integer
            sage: m^2
            WordMorphism('a->abba,b->baab')
            sage: m^3
            WordMorphism('a->abbabaab,b->baababba')
            sage: m^-2
            Traceback (most recent call last):
              ...
            ValueError: exponent (-2) must be strictly positive
            sage: n = WordMorphism('a->ba,b->abc')
            sage: n^1
            WordMorphism('a->ba,b->abc')
            sage: n^2
            Traceback (most recent call last):
              ...
            TypeError: cannot apply to incompatible set
        """
        #If exp is not an integer
        if not isint(exp):
            raise ValueError, "exponent (%s) must be an integer" %exp

        #If exp is negative
        elif exp <= 0:
            raise ValueError, "exponent (%s) must be strictly positive" %exp
        
        #Base of induction
        elif exp == 1:
            return self
        
        else:
            nexp = int(exp / 2)
            over = exp % 2
            res = (self * self) ** nexp
            if over == 1:
                res *= self
            return res
            
    def _latex_(self):
        r"""        
        Return latex representation of this morphism.
        
        EXAMPLES:
            sage: tm = WordMorphism('a->ab,b->ba'); print tm._latex_()
            \begin{array}{cccl}
            \varphi: & \{a, b\}^* & \rightarrow & \{a, b\}^* \\
            & a & \mapsto & ab \\
            & b & \mapsto & ba
            \end{array}
            sage: fibo = WordMorphism('a->ab,b->a'); print (fibo^3)._latex_()
            \begin{array}{cccl}
            \varphi: & \{a, b\}^* & \rightarrow & \{a, b\}^* \\
            & a & \mapsto & abaab \\
            & b & \mapsto & aba
            \end{array}
            sage: print (WordMorphism(''))._latex_()
            \begin{array}{cccl}
            \varphi: & \{\}^* & \rightarrow & \{\}^*
            \end{array}
            sage: print (WordMorphism('b->baa,a->ab'))._latex_()
            \begin{array}{cccl}
            \varphi: & \{a, b\}^* & \rightarrow & \{a, b\}^* \\
            & a & \mapsto & ab \\
            & b & \mapsto & baa
            \end{array}
        """
        dom_alph = self.domain().alphabet()
        cod_alph = self.codomain().alphabet()
        
        dom = str(dom_alph).replace("'","").replace('{','\\{').replace('}','\\}')
        cod = str(cod_alph).replace("'","").replace('{','\\{').replace('}','\\}')
        
        lines = ["\\varphi: & %s^* & \\rightarrow & %s^*" %(dom, cod)]
        lines += [ '& %s & \mapsto & %s' %(b, str(self(b))[6:])  for b in dom_alph ]
        s = " \\\\\n".join(lines)

        return "\\begin{array}{cccl}\n" + s + "\n\\end{array}"
        
        
    def _matrix_(self, R=None):
        r"""
        Returns the incidence matrix of the morphism over the specified ring.

        EXAMPLES:
            sage: fibo = WordMorphism('a->ab,b->a')
            sage: tm = WordMorphism('a->ab,b->ba')
            sage: Mfibo = (fibo)._matrix_(); Mfibo
            [1 1]
            [1 0]
            sage: Mtm = (tm)._matrix_(); Mtm
            [1 1]
            [1 1]
            sage: Mtm * Mfibo == (tm*fibo)._matrix_()
            True
            sage: Mfibo * Mtm == (fibo*tm)._matrix_()
            True
            sage: Mfibo.parent()
            Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
            sage: p = Mfibo.charpoly(); p
            x^2 - x - 1
            sage: p.roots(ring=RR, multiplicities=False)
            [-0.618033988749895, 1.61803398874989]
        """
        if R is None:
            return self.incidence_matrix()
        else:
            return self.incidence_matrix().change_ring(R)
        
    def incidence_matrix(self):
        r"""
        Returns the incidence matrix of the morphism. The order of the rows and
        column are given by the order defined on the alphabet of the domain
        and the codomain.
        
        The matrix returned is over the integers.  If a different ring
        is desired, use either the change_ring function or the matrix
        function.
        
        EXAMPLES:
            sage: m = WordMorphism('a->abc,b->a,c->c')
            sage: m.incidence_matrix()
            [1 1 0]
            [1 0 0]
            [1 0 1]
            sage: m = WordMorphism('a->abc,b->a,c->c,d->abbccccabca,e->abc')
            sage: m.incidence_matrix()
            [1 1 0 3 1]
            [1 0 0 3 1]
            [1 0 1 5 1]
        """
        L = []
        for b in self.domain().alphabet():
            w = self(b)
            L.append( [w.count(a) for a in self.codomain().alphabet()] )            

        from sage.rings.integer_ring import IntegerRing
        from sage.matrix.constructor import matrix
        M = matrix(IntegerRing(), L).transpose()
        return M

        
    def domain(self):
        r"""
        Return domain of the receiver.
        
        EXAMPLES:
            sage: WordMorphism('a->ab,b->a').domain()
            Words over {'a', 'b'}
            sage: WordMorphism('b->ba,a->ab').domain()
            Words over {'a', 'b'}
            sage: WordMorphism('6->ab,y->5,0->asd').domain()
            Words over {'0', '6', 'y'}
        """
        return self._domain
        
    def codomain(self):
        r"""
        Return the domain of the images.
        
        EXAMPLES :
            sage: WordMorphism('a->ab,b->a').codomain()
            Words over {'a', 'b'}
            sage: WordMorphism('6->ab,y->5,0->asd').codomain()
            Words over {'5', 'a', 'b', 'd', 's'}
        """
        return self._codomain
        
    def is_endomorphism(self):
        r"""
        Retourne true if the alphabet of the codomain is a subset
        of the one of the domain.
        
        EXAMPLES :
            sage: WordMorphism('a->ab,b->a').is_endomorphism()
            True
            sage: WordMorphism('6->ab,y->5,0->asd').is_endomorphism()
            False
        """
        # FIXME: Words object do not have a proper <= relationship
        return self.codomain() == self.domain()
        
    def images(self):
        r"""
        Return the list of all the images of the letters of the alphabet
        under the receiver.
        
        EXAMPLES :
            sage: WordMorphism('a->ab,b->a').images()
            [word: ab, word: a]
            sage: WordMorphism('6->ab,y->5,0->asd').images()
            [word: 5, word: asd, word: ab]
        """
        return self._morph.values()
        
    def reversal(self):
        r"""
        Return the reversal of the receiver.
        
        EXAMPLES :
            sage: WordMorphism('6->ab,y->5,0->asd').reversal()
            WordMorphism('0->dsa,6->ba,y->5')
            sage: WordMorphism('a->ab,b->a').reversal()
            WordMorphism('a->ba,b->a')
        """
        return WordMorphism(dict((key, w.reversal()) for (key, w) in self._morph.iteritems()))
        
    def is_empty(self):
        r"""
        Return True if the cardinality of the domain is zero and False otherwise.
        
        EXAMPLES:
            sage: WordMorphism('').is_empty()
            True
            sage: WordMorphism('a->a').is_empty()
            False
        """
        return len(self._morph) == 0    
        
    def is_erasing(self):
        r"""
        m.is_erasing() -> True or False
        
        Return True if the receiver is an erasing morphism, i.e.
        the image of a letter is the empty word.
        
        EXAMPLES :
            sage: WordMorphism('a->ab,b->a').is_erasing()
            False
            sage: WordMorphism('6->ab,y->5,0->asd').is_erasing()
            False
            sage: WordMorphism('6->ab,y->5,0->asd,7->').is_erasing()
            True
            sage: WordMorphism('').is_erasing()
            False
        """
        for image in self.images():
            if len(image) == 0:
                return True
        return False
        
    def is_identity(self):
        r"""
        Return True if the receiver is the identity morphism.
        
        EXAMPLES:
            sage: m = WordMorphism('a->a,b->b,c->c,d->e')
            sage: m.is_identity()
            False
            sage: WordMorphism('a->a,b->b,c->c').is_identity()
            True
            sage: WordMorphism('a->a,b->b,c->cb').is_identity() 
            False
            sage: m = WordMorphism('a->b,b->c,c->a')              
            sage: (m^2).is_identity()
            False
            sage: (m^3).is_identity()
            True
            sage: (m^4).is_identity()
            False
            sage: WordMorphism('').is_identity()  
            True
        """
        if self.domain() != self.codomain():
            return False
            
        for letter in self.domain().alphabet():
            if self(letter) != self.codomain()(letter):
                return False
        return True
        
    def is_involution(self):
        r"""
        Returns True if the receiver is an involution, i.e. its square
        is the identity.
        
        EXAMPLES:
            sage: WordMorphism('a->b,b->a').is_involution()
            True
            sage: WordMorphism('').is_involution()  
            True
        """
        return (self*self).is_identity()
        
    def conjugate(self, pos):
        r"""
        Return the morphism where each image of the receiver is conjugate 
        of parameter pos.
        
        Retourne le morphisme dont toutes les images ont etes conjuguees de pos.
        
        EXAMPLES :
            sage: m = WordMorphism('a->abcde')
            sage: m.conjugate(0) == m
            True
            sage: m.conjugate(1)            
            WordMorphism('a->bcdea')
            sage: m.conjugate(3)
            WordMorphism('a->deabc')
            sage: WordMorphism('').conjugate(4)
            WordMorphism('')
            sage: m = WordMorphism('a->abcde,b->xyz')
            sage: m.conjugate(2)
            WordMorphism('a->cdeab,b->zxy')
        """
        return WordMorphism(dict((key, w.conjugate(pos)) for (key, w) in self._morph.iteritems()))
        
    def has_left_conjugate(self):
        r"""     
        Return true if all the non empty images of the receiver begins with the same letter.
        
        Retourne vrai si toutes les images non vides commencent par la meme lettre.
        
        EXAMPLES:
            sage: m = WordMorphism('a->abcde,b->xyz')
            sage: m.has_left_conjugate()
            False
            sage: WordMorphism('b->xyz').has_left_conjugate()
            True
            sage: WordMorphism('').has_left_conjugate()      
            True
            sage: WordMorphism('a->,b->xyz').has_left_conjugate()
            True
            sage: WordMorphism('a->abbab,b->abb').has_left_conjugate()    
            True
            sage: WordMorphism('a->abbab,b->abb,c->').has_left_conjugate()    
            True
        """
        I = ifilterfalse(FiniteWord.is_empty, self.images())
        
        try:
            letter = I.next()[0]
        except StopIteration:
            return True

        #Compare the first letter of all the non empty images
        for image in I:
            if image[0] != letter:
                return False
                
        return True
        
    def has_right_conjugate(self):
        r"""     
        Return true if all the non empty images of the receiver ends with the same letter.
        
        Retourne vrai si toutes les images non vide terminent par la meme lettre.
        
        EXAMPLES:
            sage: m = WordMorphism('a->abcde,b->xyz')
            sage: m.has_right_conjugate()
            False
            sage: WordMorphism('b->xyz').has_right_conjugate()
            True
            sage: WordMorphism('').has_right_conjugate()      
            True
            sage: WordMorphism('a->,b->xyz').has_right_conjugate()
            True
            sage: WordMorphism('a->abbab,b->abb').has_right_conjugate()    
            True
            sage: WordMorphism('a->abbab,b->abb,c->').has_right_conjugate()
            True
        """                
        return self.reversal().has_left_conjugate()
        
    def list_of_conjugates(self):
        r"""     
        Retourne une liste des morphismes conjugues du receveur
        obtenus en conjuguant les prefixes (et suffixes) communs
        de chacune des images.
        
        Return the list of all the conjugate morphisms of the receiver obtain
        by taking the conjugate of the common prefixes and suffixes of all
        the images.
        
        DEFINITION (from [1]):
        Recall from Lothaire [2] (Section 2.3.4) that $\varphi$ is \emph{right conjugate} of $\varphi'$, noted $\varphi\triangleleft\varphi'$, if there exists $u \in \Sigma^*$ such that $$\varphi(\alpha)u = u\varphi'(\alpha), \quad \textrm{for all } \alpha \in \Sigma$$, or equivalently that $\varphi(x)u = u\varphi'(x)$, for all words $x \in \Sigma^*$. Clearly, this relation is not symmetric so that we say that two morphisms $\varphi$ and $\varphi'$ are \emph{conjugate}, noted $\varphi\bowtie\varphi'$, if $\varphi\triangleleft\varphi'$ or $\varphi'\triangleleft\varphi$. It is easy to see that conjugacy of morphisms is an equivalence relation. 
        
        REFERENCES:
        [1] A. Blondin-Mass\'e, S. Brlek, S. Labb\'e, Palindromic lacunas of the Thue-Morse word, 2008, to appear.
        [2] M. Lothaire, Algebraic Combinatorics on words, Cambridge University Press, 2002.

        
        EXAMPLES:
            sage: m = WordMorphism('a->abbab,b->abb')                       
            sage: m.list_of_conjugates()
            [WordMorphism('a->babba,b->bab'),
             WordMorphism('a->abbab,b->abb'),
             WordMorphism('a->bbaba,b->bba'),
             WordMorphism('a->babab,b->bab'),
             WordMorphism('a->ababb,b->abb'),
             WordMorphism('a->babba,b->bba'),
             WordMorphism('a->abbab,b->bab')]
            sage: WordMorphism('a->aaa,b->aa').list_of_conjugates()
            [WordMorphism('a->aaa,b->aa')]
            sage: WordMorphism('').list_of_conjugates()            
            [WordMorphism('')]
            sage: WordMorphism('a->aba,b->aba').list_of_conjugates()
            [WordMorphism('a->baa,b->baa'),
             WordMorphism('a->aab,b->aab'),
             WordMorphism('a->aba,b->aba')]
            sage: WordMorphism('a->abb,b->abbab,c->').list_of_conjugates()
            [WordMorphism('a->bab,b->babba,c->'),
             WordMorphism('a->abb,b->abbab,c->'),
             WordMorphism('a->bba,b->bbaba,c->'),
             WordMorphism('a->bab,b->babab,c->'),
             WordMorphism('a->abb,b->ababb,c->'),
             WordMorphism('a->bba,b->babba,c->'),
             WordMorphism('a->bab,b->abbab,c->')]
        """
        if self.is_empty():
            return [self]
        
        #Construire la liste c des morphismes conjugues
        c = []
        m = self
        c.append(m)
        while(m.has_left_conjugate()):
            m = m.conjugate(1)
            if m == self:
                break
            c.append(m)
        m = self
        while(m.has_right_conjugate()):
            m = m.conjugate(-1)
            if m == self:
                break
            c.insert(0, m)
                        
        #Construire la liste d des morphismes distincts
        d = []
        for m in c:
            if m not in d:
                d.append(m)
        return d

